package com.zhanghp.class040;

/**
 * N皇后问题<br/>
 * 测试链接 : https://leetcode.cn/problems/n-queens-ii/
 *
 * @author zhanghp
 * @since 2024/6/29 11:01
 */
public class Code01_NQueens {

    public int totalNQueens(int n) {
        // 边界处理
        if (n < 1) {
            return 0;
        }
        return count(0, new int[n], n);
    }

    public int count(int row, int[] path, int n) {
        // row 从 0...n-1
        // 达到临界值，说明存在一组解
        if (row == n) {
            return 1;
        }
        int ans = 0;
        // 从0...n-1列开始试解
        for (int column = 0; column < n; column++) {
            // 检查 当前行，和以前路径是否产生在同一对角线上
            if (check(row, column, path)) {

                // 把当前列符合添加path，方便后续行结果排列组合
                path[row] = column;
                // 下一行

                // 判断是否当前列符合
                // 判断当前列是否符合，那就需要之前的路径来比对
                // path是n的长度，所以还需要限制，for循环的终端最大数量，所以需要row，来矫正
                // 当row递归回第一行时，那么path会有数据，也不会影响，因为有row限制
                ans += count(row + 1, path, n);
            }
        }
        return ans;
    }

    public boolean check(int row, int column, int[] path) {
        // 获取当前行之前行的路径列信息，进行for循环
        for (int k = 0; k < row; k++) {
            // 同列 || 同对角线（|横-横|=|竖-竖|）
            if (path[k] == column || Math.abs(k - row) == Math.abs(path[k] - column)) {
                return false;
            }
        }
        return true;
    }

}
